ProbSparse Self-Attention and Generative Multi-Horizon Decoding

An Undergraduate Guide to O(L ln L) Sparse Transformers, Conv1D Distilling, and Multi-Step Error Accumulation

Author

Deepak Bastola

Published

October 23, 2026

1 How Do Transformers Scale to Long Multivariate Sequences?

In a standard Transformer (Vaswani et al., 2017), every query token $\mathbf{q}_i$ computes dot-product attention against every key token $\mathbf{k}_j$ across a sequence of length $L_Q$, forming an $L_Q \times L_Q$ matrix with $\mathcal{O}(L_Q^2)$ computational complexity. Yet when you inspect the learned attention weights on time-series data, most queries produce nearly flat, uniform distributions, while only a handful of active queries lock onto sharp structural events or turning points.

The Informer architecture (Zhou et al., 2021) exploits this sparsity through three elegant ideas that make an ideal undergraduate case study in sequence architecture design:

ProbSparse Query Selection ($\mathcal{O}(L_Q \ln L_Q)$): Selecting only the top $u = \lceil c \ln L_Q \rceil$ most informative queries using a fast max-mean Kullback-Leibler divergence approximation.
Self-Attention Distilling (Conv1D + MaxPool1D): Halving sequence length between encoder layers to filter out high-frequency noise.
One-Shot Generative Decoding: Predicting all $H$ future steps in a single forward pass rather than feeding noisy predictions back into the network one step at a time.

2 Step 1: Why ProbSparse Requires Sufficient Sequence Length ($L_Q = 96 \implies u = 14$)

To measure how far query $\mathbf{q}_i$’s attention distribution departs from a flat uniform distribution without computing all $L_Q^2$ exponentials, Informer uses the max-mean sparsity measurement:

\[\overline{M}(\mathbf{q}_i, \mathbf{K}) = \max_{j}\!\left\{\frac{\mathbf{q}_i \mathbf{k}_j^\top}{\sqrt{d_k}}\right\} - \frac{1}{L_K}\sum_{j=1}^{L_K} \frac{\mathbf{q}_i \mathbf{k}_j^\top}{\sqrt{d_k}}, \qquad u = \lceil c \ln L_Q \rceil.\]

A Crucial Mathematical Lesson on Lookback Length $L_Q$: Suppose a student sets the lookback window to only $L_Q = 10$ time steps with sampling factor $c = 5$. Then $u = \lceil 5 \ln 10 \rceil = 12 > 10$, so ProbSparse selects 100% of the queries and degenerates into ordinary full attention!
Non-Degenerate Sparsity at $L_Q = 96$: With an encoder window of $L_Q = 96$ steps and $c = 3$, ProbSparse selects exactly $u = \lceil 3 \ln 96 \rceil = 14$ active queries ($14.58\%$ of the sequence, threshold $M^* = 6.00$) and assigns the remaining $82$ lazy queries the mean value vector $\bar{\mathbf{V}}$. Paired with Conv1D distilling ($96 \to 48 \to 24$), this cuts measured inference latency from $3.12\text{ ms/batch}$ (Full Attention) to $1.84\text{ ms/batch}$.

3 Step 2: Multi-Horizon Error Accumulation ($H \in \{1, \dots, 16\}$) and Width Ablation

When forecasting a 4-channel multivariate price bar (Open, High, Low, Close) over $H = 1$ to $16$ steps ahead across $5$ random seeds (using a leakage-free 70/15/15 split with scalers fit strictly on the training set), we observe two clear phenomena:

Martingale Baseline vs. Neural Sequence Models: On unadjusted daily price levels, the No-Change Random Walk error grows as $\sigma_1 \sqrt{H}$ ($\$1.629$ at $H=1$, $\$4.817$ at $H=8$, $\$7.085$ at $H=16$). While no neural network beats the random walk on raw martingale price levels, within the neural sequence family, one-shot generative decoding and ProbSparse regularization reduce $H = 16$ MSE by $33.1\%$ relative to recursive Seq2Seq LSTMs ($\$7.136$ vs. $\$8.667$) and by $35.5\%$ relative to Full-Attention Transformers ($\$7.136$ vs. $\$8.888 \pm 0.142$, which overfit noisy all-pairs token correlations).
Systematic Ablation Across Embedding Widths $d_{\mathrm{model}} \in \{64, 128, 256, 360, 512\}$: Evaluating both distilled and non-distilled encoders across all five widths confirms that Conv1D distilling lowers validation and test error at every single width, with validation performance selecting $d_{\mathrm{model}} = 256$ ($\$1.639 \pm 0.001$ with distilling vs. $\$1.693 \pm 0.004$ without distilling).

Architecture ($L_Q = 96$, 5-Seed Mean $\pm$ SD)	Active Queries / Latency	$H=1$ RMSE	$H=8$ RMSE	$H=16$ RMSE	Pedagogical Takeaway
Benchmark: No-Change Random Walk (Persistence)	$\mathcal{O}(1)$ Baseline	$1.629$	$4.817$	$7.085$	Martingale baseline scales as $\sigma_1 \sqrt{H}$
ProbSparse Informer ($d_{\mathrm{model}}=256$, Distilling)	$u=14 / 96$ ($1.84\text{ ms}$)	$1.639 \pm 0.001$	$4.906 \pm 0.008$	$7.136 \pm 0.028$	$+33.1\%$ $H=16$ MSE reduction vs. recursive LSTM
ProbSparse Informer ($d_{\mathrm{model}}=256$, No Distilling)	$u=14 / 96$ ($2.41\text{ ms}$)	$1.693 \pm 0.004$	$5.060 \pm 0.029$	$7.516 \pm 0.064$	Omitting $\mathrm{Conv1D}$ distilling increases multi-step variance
Autoregressive Seq2Seq LSTM	Recursive $\mathcal{O}(L)$	$1.631$	$5.517$	$8.667$	Step-by-step rollouts compound prediction errors
Canonical Full-Attention Transformer ($d_{\mathrm{model}}=256$)	$96 / 96$ ($3.12\text{ ms}$)	$1.667 \pm 0.002$	$5.650 \pm 0.057$	$8.888 \pm 0.142$	Dense $96\times 96$ attention overfits noisy price fluctuations

4 Exploring Further: Research Directions

Research Track	Core Question to Investigate	Tools & Methods
1. Enforcing Geometric Bar-Ordering Constraints	How can we parameterize the decoder output layer via positive softplus increments so predicted bars always satisfy $\mathrm{Low} \le \min(\mathrm{Open}, \mathrm{Close}) \le \max(\mathrm{Open}, \mathrm{Close}) \le \mathrm{High}$?	Constrained Neural Output Layers, Differentiable Parametrization
2. Seasonal Physical & Energy Benchmarks	How much positive skill over persistence does ProbSparse Informer achieve on strongly periodic hourly temperature and electrical grid load datasets (`ETT`)?	Long-Sequence Time-Series Forecasting ($L_Q = 336$)
3. Sparse Transformers vs. Patch Linear Mixers	When do lightweight patch/linear architectures (`PatchTST`, `DLinear`) match or outperform attention models on noisy sequences?	Architecture Benchmarking, Diebold-Mariano Tests

Architecture (\(L_Q = 96\), 5-Seed Mean \(\pm\) SD)	Active Queries / Latency	\(H=1\) RMSE	\(H=8\) RMSE	\(H=16\) RMSE	Pedagogical Takeaway
Benchmark: No-Change Random Walk (Persistence)	\(\mathcal{O}(1)\) Baseline	\(1.629\)	\(4.817\)	\(7.085\)	Martingale baseline scales as \(\sigma_1 \sqrt{H}\)
ProbSparse Informer (\(d_{\mathrm{model}}=256\), Distilling)	\(u=14 / 96\) (\(1.84\text{ ms}\))	\(1.639 \pm 0.001\)	\(4.906 \pm 0.008\)	\(7.136 \pm 0.028\)	\(+33.1\%\) \(H=16\) MSE reduction vs. recursive LSTM
ProbSparse Informer (\(d_{\mathrm{model}}=256\), No Distilling)	\(u=14 / 96\) (\(2.41\text{ ms}\))	\(1.693 \pm 0.004\)	\(5.060 \pm 0.029\)	\(7.516 \pm 0.064\)	Omitting \(\mathrm{Conv1D}\) distilling increases multi-step variance
Autoregressive Seq2Seq LSTM	Recursive \(\mathcal{O}(L)\)	\(1.631\)	\(5.517\)	\(8.667\)	Step-by-step rollouts compound prediction errors
Canonical Full-Attention Transformer (\(d_{\mathrm{model}}=256\))	\(96 / 96\) (\(3.12\text{ ms}\))	\(1.667 \pm 0.002\)	\(5.650 \pm 0.057\)	\(8.888 \pm 0.142\)	Dense \(96\times 96\) attention overfits noisy price fluctuations

ProbSparse Self-Attention and Generative Multi-Horizon Decoding

1 How Do Transformers Scale to Long Multivariate Sequences?

2 Step 1: Why ProbSparse Requires Sufficient Sequence Length (\(L_Q = 96 \implies u = 14\))

3 Step 2: Multi-Horizon Error Accumulation (\(H \in \{1, \dots, 16\}\)) and Width Ablation

4 Exploring Further: Research Directions